Skip to content
概述
给定 m 个数组，每个数组已经按升序排列。需要从两个不同的数组中各自取出一个元素，使得这两个元素的绝对差最大。返回这个最大距离。
LeetCode 624 是一道算法题，但其遍历模式——在单次扫描中维护历史极值并与当前项组合——在类似问题中也有应用。
基本概念
- 已排序数组：每个子数组的最小值在索引 0，最大值在索引
length - 1。这是解决该问题的前提。 - 跨数组约束：选取的两个元素必须来自不同的子数组。如果忽略该约束，直接在所有元素中取全局最大值和最小值即可得到答案。
- 极值组合：对于任意两个数组 A 和 B，可能产生最大距离的组合只有两种——(A 的最大值 − B 的最小值) 或 (B 的最大值 − A 的最小值)。绝对值形式等价于
max(|maxA - minB|, |maxB - minA|)。
工作原理
核心思路是一次遍历，顺序处理每个数组。遍历时，维护两个变量：
minSoFar：已经处理过的数组中的最小元素。maxSoFar：已经处理过的数组中的最大元素。
对于当前数组，取其最小值 curMin 和最大值 curMax。用下列两个候选值更新结果：
|curMax - minSoFar|— 当前数组的最大值与历史最小值之差的绝对值。|maxSoFar - curMin|— 历史最大值与当前数组的最小值之差的绝对值。
这实际上枚举了当前数组与之前所有数组的所有可能极值组合。因为数组内部已经有序，只使用极值不会漏掉最优解。
关键约束：必须先计算距离，再更新历史极值。如果顺序颠倒，当前数组的极值会进入历史记录，进而可能与同一数组的另一个极值计算距离，违反“必须来自不同数组”的条件。
整个过程遍历一次数组，时间复杂度 O(m)，m 是数组个数。空间复杂度 O(1)，只用了常数个额外变量。
基本用法
算法本身不依赖额外 API，主要以函数形式实现，输入为二维数组，输出为最大距离。
示例
Node.js
ts
function maxDistance(arrays: number[][]): number {
let result = 0;
let minSoFar = arrays[0][0];
let maxSoFar = arrays[0][arrays[0].length - 1];
for (let i = 1; i < arrays.length; i++) {
const current = arrays[i];
const curMin = current[0];
const curMax = current[current.length - 1];
const dist1 = Math.abs(curMax - minSoFar);
const dist2 = Math.abs(maxSoFar - curMin);
result = Math.max(result, dist1, dist2);
minSoFar = Math.min(minSoFar, curMin);
maxSoFar = Math.max(maxSoFar, curMax);
}
return result;
}执行示例：arrays = [[1, 2, 3], [4, 5], [6, 7, 8]]
- 初始化：
minSoFar = 1，maxSoFar = 3，result = 0。 - 处理第二个数组
[4, 5]：curMin = 4，curMax = 5。计算dist1 = |5 - 1| = 4，dist2 = |3 - 4| = 1，result = 4。随后更新minSoFar = min(1, 4) = 1，maxSoFar = max(3, 5) = 5。 - 处理第三个数组
[6, 7, 8]：curMin = 6，curMax = 8。计算dist1 = |8 - 1| = 7，dist2 = |5 - 6| = 1，result更新为 7。最终返回 7。
Java
java
public int maxDistance(List<List<Integer>> arrays) {
int result = 0;
int minSoFar = arrays.get(0).get(0);
int maxSoFar = arrays.get(0).get(arrays.get(0).size() - 1);
for (int i = 1; i < arrays.size(); i++) {
List<Integer> current = arrays.get(i);
int curMin = current.get(0);
int curMax = current.get(current.size() - 1);
result = Math.max(result, Math.abs(curMax - minSoFar));
result = Math.max(result, Math.abs(maxSoFar - curMin));
minSoFar = Math.min(minSoFar, curMin);
maxSoFar = Math.max(maxSoFar, curMax);
}
return result;
}Python
python
def maxDistance(arrays):
result = 0
min_so_far = arrays[0][0]
max_so_far = arrays[0][-1]
for arr in arrays[1:]:
cur_min, cur_max = arr[0], arr[-1]
result = max(result, abs(cur_max - min_so_far),
abs(max_so_far - cur_min))
min_so_far = min(min_so_far, cur_min)
max_so_far = max(max_so_far, cur_max)
return result注意点
- 数组的有序性是隐含前提。如果输入未排序，需要将每个子数组分别排序（或单独扫描得到极值），这会引入额外开销，并使上述示例的直接取首尾元素的方式不再适用。
- 计算距离时使用了绝对值。因为数组有序，
curMax - minSoFar可能为正或负，绝对值保证距离非负。在实际问题中也可直接取max(curMax - minSoFar, maxSoFar - curMin)，后者在有序数组下自然保证非负。为逻辑清晰，示例保留了abs。 - 更新历史极值和计算答案的顺序不可颠倒。一旦颠倒，同一数组的最大值与最小值可能错误地参与距离计算。
限制
- 时间复杂度 O(m)，m 是外层数组的长度。每个数组只访问一次。
- 空间复杂度 O(1)，不依赖额外的数据结构。
- 输入至少包含两个数组，且每个数组不为空（题目隐含约束）。
应用
“遍历时维护历史极值并与当前元素组合”的模式在类似问题中反复出现，例如：
- 股票买卖最大利润（单次交易）：遍历价格序列，维护历史最低价，每天计算当前价与历史最低价的差值。
- 求数组中两个元素的最大差值（后减前）：同样维护历史最小值。
- 多个有序数据流中取极值组合，如日志时间戳对齐、区间合并前的最大间隙等。
这些场景的共同特征是需要从不同集合中选取元素以最大化某种差值，并且数据天然有序或可通过预处理排序。